{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-ary Tree Postorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: postorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 叉树的后序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 n&nbsp;叉树的根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;，返回 <em>其节点值的<strong> 后序遍历</strong></em> 。</p>\n",
    "\n",
    "<p>n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 <code>null</code> 分隔（请参见示例）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png\" style=\"height: 193px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>[5,6,3,2,4,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"height: 269px; width: 296px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出：</strong>[2,6,14,11,7,3,12,8,4,13,9,10,5,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点总数在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>n 叉树的高度小于或等于 <code>1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>递归法很简单，你可以使用迭代法完成此题吗?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-ary-tree-postorder-traversal](https://leetcode.cn/problems/n-ary-tree-postorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-ary-tree-postorder-traversal](https://leetcode.cn/problems/n-ary-tree-postorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        if root is None: return []\n",
    "        queue = collections.deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            curr = queue.pop()\n",
    "            result.append(curr.val)\n",
    "            for child in curr.children:\n",
    "                queue.append(child)\n",
    "        return result[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        stack, res = [root,], []\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            res.append(cur.val)\n",
    "            stack.extend(cur.children[::])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> 'List[int]':\n",
    "        return [i for j in root.children for i in self.postorder(j)] + [root.val] if root else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> 'List[int]':\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.children:\n",
    "            return [root.val]\n",
    "        result = []\n",
    "        for child in root.children:\n",
    "            result += self.postorder(child)\n",
    "        result += [root.val]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        tmp = []\n",
    "        for i in root.children:\n",
    "            tmp += self.postorder(i)\n",
    "        return tmp + [root.val]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        stack = [root]\n",
    "        out = []\n",
    "\n",
    "        while stack != []:\n",
    "            # print(stack, stack[-1], out, stack[-1].children)\n",
    "            if stack[-1].children != None:\n",
    "                temp = stack[-1]\n",
    "                i = len(temp.children)-1\n",
    "                while i > -1:\n",
    "                    stack.append(temp.children[i])\n",
    "                    i -= 1\n",
    "                temp.children = None\n",
    "                # print(stack[-1].children)\n",
    "            else:\n",
    "                a = stack[-1]\n",
    "                stack = stack[:-1]\n",
    "                out.append(a.val)\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        if root is None: return []\n",
    "        stack, output = [root, ], []\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            if root is not None:\n",
    "                output.append(root.val)\n",
    "            for c in root.children:\n",
    "                stack.append(c)\n",
    "        return output[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "\n",
    "    def postorder(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if not node: continue\n",
    "            res.append(node.val)\n",
    "            for child in node.children:\n",
    "                stack.append(child)\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        # method 1 递归\n",
    "        # res = []\n",
    "        # def helper(node: 'Node'):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     for children in node.children:\n",
    "        #         helper(children)\n",
    "        #     res.append(node.val)\n",
    "            \n",
    "        # helper(root)\n",
    "        # return res\n",
    "\n",
    "        # method 2 迭代\n",
    "        res = []\n",
    "        stack = [(0,root)]\n",
    "        while stack:\n",
    "            isPass, node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if isPass:\n",
    "                res.append(node.val)\n",
    "                continue\n",
    "            stack.append((1,node))\n",
    "            for children in node.children[::-1]:\n",
    "                stack.append((0,children))\n",
    "            \n",
    "\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        # 递归\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        for i in root.children:\n",
    "            res.extend(self.postorder(i))\n",
    "        res.append(root.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        ans = []\n",
    "        def order(root,ans):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.children:\n",
    "                for node in root.children:\n",
    "                    order(node,ans)\n",
    "            ans.append(root.val)\n",
    "        order(root,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        resultList = []\n",
    "        if root is None:\n",
    "            return resultList\n",
    "\n",
    "        q = [root]\n",
    "        dequeueNodeList = []\n",
    "        while len(q) != 0:\n",
    "            tempNode = q[0]\n",
    "            childrenLength = len(tempNode.children)\n",
    "            # print(childrenLength)\n",
    "            # print('resultList: ',resultList)\n",
    "            if childrenLength == 0:\n",
    "                node = q.pop(0)\n",
    "                resultList.append(node.val)\n",
    "                dequeueNodeList.append(node)\n",
    "                if len(q) == 0:\n",
    "                    break\n",
    "                tempNode = q[0]\n",
    "                childrenLength = len(tempNode.children)\n",
    "            if tempNode in dequeueNodeList:\n",
    "                continue\n",
    "            elif set(tempNode.children).issubset(dequeueNodeList):\n",
    "                # print(1)\n",
    "                resultList.append(tempNode.val)\n",
    "                dequeueNodeList.append(q.pop(0))\n",
    "                continue\n",
    "            if childrenLength != 0:\n",
    "                for i in range(childrenLength):\n",
    "                    q.insert(i, tempNode.children[i])\n",
    "        return resultList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import chain\n",
    "class Solution:\n",
    "\tdef postorder(self,root):\n",
    "\t\tif root:\n",
    "\t\t\treturn chain(*map(self.postorder,root.children),(root.val,))\n",
    "\t\treturn []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        #迭代法\n",
    "        if not root: return []\n",
    "        stack, res = [root], []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            n = len(node.children)\n",
    "            for i in range(n): stack.append(node.children[i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        nodeStack = []\n",
    "        nodeStack.append(root)\n",
    "        while nodeStack:\n",
    "            node = nodeStack.pop()\n",
    "            result.append(node.val)\n",
    "            for chl in node.children:\n",
    "                nodeStack.append(chl)\n",
    "        return result[::-1]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            for ch in node.children:\n",
    "                dfs(ch)\n",
    "            res.append(node.val)\n",
    "\n",
    "        dfs(root)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        # 迭代 使用双向队列 -不使用双向队列更加单\n",
    "        # if root == None:\n",
    "        #     return None\n",
    "        # queue = collections.deque()\n",
    "        # queue.append(root)\n",
    "        # reslist = []\n",
    "        # while (len(queue) != 0):\n",
    "        #     topnode = queue[0]\n",
    "        #     if topnode.children == None:\n",
    "        #         reslist.append(topnode.val)\n",
    "        #         queue.popleft()\n",
    "        #     else:\n",
    "        #         childlist = topnode.children\n",
    "        #         for i in range(len(childlist) - 1, -1, -1):\n",
    "        #             queue.appendleft(childlist[i])\n",
    "        #         topnode.children = None\n",
    "        # return reslist\n",
    "\n",
    "        #迭代不使用双向队列\n",
    "        if root == None:\n",
    "            return None\n",
    "        #queue = collections.deque()\n",
    "        queue=[]\n",
    "        queue.append(root)\n",
    "        reslist = []\n",
    "        while (len(queue) != 0):\n",
    "            topnode = queue[-1]\n",
    "            if topnode.children == None:\n",
    "                reslist.append(topnode.val)\n",
    "                queue.pop()\n",
    "            else:\n",
    "                childlist = topnode.children\n",
    "                for i in range(len(childlist) - 1, -1, -1):\n",
    "                    queue.append(childlist[i])\n",
    "                topnode.children = None\n",
    "        return reslist\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        prev = -1\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append((root,0))\n",
    "                if root.children:\n",
    "                    root = root.children[0]\n",
    "                else:\n",
    "                    root = None\n",
    "            \n",
    "            cur, index = stack.pop()\n",
    "            if cur.children and index != len(cur.children) - 1:\n",
    "                stack.append((cur, index + 1))\n",
    "                root = cur.children[index + 1]\n",
    "            elif not cur.children or index == len(cur.children) -1:\n",
    "                res.append(cur.val)\n",
    "                root = None\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            for child in root.children:\n",
    "                helper(child)\n",
    "            result.append(root.val)\n",
    "\n",
    "        helper(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        # return list(chain(*[self.postorder(child) for child in root.children])) + [root.val] if root else []\n",
    "        return [node for child in root.children for node in self.postorder(child)] + [root.val] if root else []\n",
    "        # return (list(reduce(list.__add__, [self.postorder(child) for child in root.children])) if root.children else []) + [root.val] if root else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        result = self.traversal(root)\n",
    "        return result\n",
    "\n",
    "    def traversal(self,cur: 'Node'):\n",
    "        if not cur:\n",
    "            return []\n",
    "\n",
    "        child_res = []\n",
    "        for child in cur.children:\n",
    "            child_res += (self.traversal(child))\n",
    "        \n",
    "        result = child_res + [cur.val]\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        # 递归先序遍历\n",
    "        res = []\n",
    "\n",
    "        def backtracking(node):\n",
    "            # 终止条件\n",
    "            if not root:\n",
    "                return\n",
    "            # 单层递归\n",
    "            for child in node.children:\n",
    "                backtracking(child)\n",
    "            res.append(node.val)\n",
    "        backtracking(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def postorder(self, root: 'Node') -> List[int]:\n",
    "        def bl(r=Node()):\n",
    "            if not r:return []\n",
    "            l=[]\n",
    "            for i in r.children:\n",
    "                l=l+bl(i)\n",
    "            return l+[r.val]\n",
    "        return bl(root)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
